public class Main {
    /* n;
    List<String> ret;
    StringBuffer path;
     left;
     right;
    public List<String> generateParenthesis( _n) {
        n = _n;
        ret = new ArrayList<>();
        path = new StringBuffer();
        left = 0;
        right = 0;
        dfs();
        return ret;
    }
    void dfs() {
        //先安排左括号 再安排右括号
        //所以结尾处一定是由 ) 来首尾的
        if(right == n) {
            ret.add(path.toString());
            return;
        }

        if(left < n){
            //递归左
            path.append('(');
            left++;
            dfs();
            //恢复现场
            path.deleteCharAt(path.length() - 1);
            left--;
        }
        if(right < left) {
            //递归右
            path.append(')');
            right++;
            dfs();
            //恢复现场
            path.deleteCharAt(path.length() - 1);
            right--;
        }
    }*/

    /*List<List<Integer>> ret;
    List<Integer> path;
     n;
     k;

    public List<List<Integer>> combine( _n,  _k) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        n = _n;
        k = _k;
        dfs(0);
        return ret;
    }

    void dfs( pos) {
        if (path.size() == k) {
            ret.add(new ArrayList<>(path));
            return;
        }
        for ( i = pos; i < n; i++) {
            path.add(i+1);
            dfs(i + 1);
            //恢复现场
            path.remove(path.size() - 1);
        }
    }*/

    /**
     * 目标和 path 作为参数 和 全局变量两种写法
     */
   /* class Solution {
         path, aim ,ret;
        public  findTargetSumWays([] nums,  target) {
            path = 0;
            ret = 0;
            aim = target;
            dfs(nums, 0);
            return ret;
        }

        public void dfs([] nums,  pos) {
            //递归结束条件
            if(pos == nums.length) {
                if(path == aim) ret++;
                return;
            }
            //递归左边
            path += nums[pos];
            dfs(nums, pos + 1);
            //恢复现场
            path -= nums[pos];
            //递归右边
            path -= nums[pos];
            dfs(nums, pos + 1);
            //恢复现场
            path += nums[pos];
        }
    }*/
    /* aim ,ret;
    public  findTargetSumWays([] nums,  target) {
        ret = 0;
        aim = target;
        dfs(nums, 0, 0);
        return ret;
    }

    public void dfs([] nums,  pos,  path) {
        //递归结束条件
        if(pos == nums.length) {
            if(path == aim) ret++;
            return;
        }
        //递归左边
        dfs(nums, pos + 1, path + nums[pos]);
        //递归右边
        dfs(nums, pos + 1, path - nums[pos]);
    }*/

    /* *//**
     * 组合数 枚举数组位置
     *//*
    List<List<Integer>> ret;
    List<Integer> path;
     aim;
    public List<List<Integer>> combinationSum([] nums,  target) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        aim = target;
        //此处的dfs是递归数组的每个位置

        dfs(nums, 0, 0);
        return ret;
    }

    public void dfs([] nums,  pos,  sum) {
        if(sum == aim) {
            ret.add(new ArrayList<>(path));
            return;
        }
        if(sum > aim || pos == nums.length) {
            return;
        }
        //递归到某个位置后, 需要枚举多个量
        for( i = pos; i < nums.length; i++ ) {
            path.add(nums[i]);
            dfs(nums, i, sum + nums[i]);
            path.remove(path.size() - 1);
        }
    }

    *//***
     * 枚举某个数出现的次数
     *//*
    //针对每个数枚举多次的思路
    List<List<Integer>> ret;
    List<Integer> path;
     aim;
    public List<List<Integer>> combinationSum([] nums,  target) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        aim = target;
        //此处的dfs是递归数组的每个位置

        dfs(nums, 0, 0);
        return ret;
    }

    public void dfs([] nums,  pos,  sum) {
        if(sum == aim) {
            ret.add(new ArrayList<>(path));
            return;
        }
        if(sum > aim || pos == nums.length) {
            return;
        }
        //递归到某个位置后, 需要枚举多个量
        for( k = 0; k * nums[pos] > aim; k++) {
            if(k != 0) path.add(nums[pos]);
            dfs(nums, pos + 1, sum + nums[pos] * k);
            //注意这里面不用恢复现场
            //如果这恢复了现场 那么 就无法达到多个数 1 1 1 这种, 因为你已经清楚掉一部分了
            //而每次add只能add一个 如果恢复现场 要怎么达到这种效果呢?
        }
        //恢复现场
        for( k = 1; nums[pos] * k < aim; k++) {
            path.remove(path.size() - 1);
        }
    }*/

    /*List<String> ret;
    StringBuilder path;

    public List<String> letterCasePermutation(String s) {
        ret = new ArrayList<>();
        path = new StringBuilder();
        dfs(s, 0);
        return ret;
    }

    public void dfs(String s,  pos) {
        if(pos == s.length()) {
            ret.add(path.toString());
            return;
        }
        char ch = s.charAt(pos);
        //不变
        path.append(ch);
        dfs(s, pos + 1);
        path.deleteCharAt(path.length() - 1);//恢复现场
        //改变
        if(ch >= 'A') {
            char newChar = change(ch);
            path.append(newChar);
            dfs(s, pos + 1);
            path.deleteCharAt(path.length() - 1);//恢复现场
        }
    }
    public char change(char ch) {
        if(ch >= 'a' && ch <= 'z') {
            return ch -= 32;
        } else {
            return ch += 32;
        }
    }

    public static void main(String[] args) {
         a = 1;
        Main t = new Main();
        List<String > ret = t.letterCasePermutation("a1b2");
        System.out.prln(ret);
    }*/


    /*boolean[] check;
     ret;
    public  countArrangement( n) {
        check = new boolean[n + 1];
        dfs(1,n);
        return ret;
    }
    public void dfs( pos,  n) {
        if(pos == n + 1) {
            ret ++;
            return;
        }
        for( i = 1; i <= n; i++) {
            //先判断是否该数是否被选过了
            if(check[i] == false && (i % pos == 0 || pos % i == 0) ) {
                check[i] = true;
                dfs(pos + 1, n);
                check[i] = false;
            }
        }
    }*/
    /**
     *
     * n皇后
     */
    /*List<List<String>> ret;
    boolean[] checkCol;
    char[][] path;
     n;
    boolean[] checkDig1;
    boolean[] checkDig2;

    public List<List<String>> solveNQueens( N) {
        n = N;
        checkCol = new boolean[N];
        ret = new ArrayList<>();
        path = new char[N][N];
        checkDig1 = new boolean[2 * N];
        checkDig2 = new boolean[2 * n];
        for ( i = 0; i < N; i++) {
            Arrays.fill(path[i], '.');
        }
        dfs(0);
        return ret;
    }

    public void dfs( row) {
        if(row == n) {
            List<String> list = new ArrayList<>();
            for( i = 0; i < n; i++) {
                list.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(list) );
        }

        for( col = 0; col < n; col++) {
            if(checkCol[col] == false && checkDig1[row - col + n] == false && checkDig2[row + col] == false) {
                path[row][col] = 'Q';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;
                dfs(row + 1);
                path[row][col] = '.';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;
            }
        }
    }

    public static void main(String[] args) {
        Main t = new Main();
        List<List<String>> ret = t.solveNQueens(4);


    }*/
    /**
     * 有效的数独
     */
    /*boolean[][] colCheck;
    boolean[][] rowCheck;
    boolean[][][] gridCheck;
    public boolean isValidSudoku(char[][] board) {
        colCheck = new boolean[9][10];
        rowCheck = new boolean[9][10];
        gridCheck = new boolean[3][3][10];
        for( i = 0; i < 9; i++) {
            for( j = 0; j < 9; j++) {

                if(board[i][j] != '.') {
                     num = board[i][j] - '0';
                    //判断是否有效
                    if(colCheck[j][num] == true || rowCheck[i][num] == true || gridCheck[i / 3][j / 3][num] == true) {
                        return false;
                    } else {
                        //有效
                        colCheck[j][num] = rowCheck[i][num] = gridCheck[i / 3][j / 3][num] = true;
                    }
                }
            }
            //有效
        }
        return true;
    }*/
    /**
     * 解数独
     */
    /*boolean[][] row;
    boolean[][] col;
    boolean[][][] grid;

    public void solveSudoku(char[][] board) {
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];
        for ( i = 0; i < 9; i++) {
            for ( j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    //是数字不需要填
                    //只需要去初始化一下bool表就行
                     num = board[i][j] - '0';
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
            }
        }
        //初始化好check后就可以吧board交给 dfs 让他去帮我们填表
        dfs(board);
    }

    public boolean dfs(char[][] board) {
        for ( i = 0; i < 9; i++) {
            for ( j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for ( num = 1; num <= 9; num++) {
                        if (!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]) {
                            board[i][j] = (char) ('0' + num);
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                            boolean ret = dfs(board);
                            if (ret == true)
                                return true;//说明此路已通
                            //说明此路不通 就要另寻道路
                            //恢复现场
                            board[i][j] = '.';
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false;
                        }
                    }
                    //如果所有的路都走遍了 都不行 那不就说明没路可行吗 也就是没有解啊 直接返回false
                    return false;
                }
            }

        }
        //所有的空格都走遍了 说明可行啊 走得通啊
        return true;
    }*/


}

class Solution {
   /* boolean[][] visit;
    int m,n;
    char[] word;
    public boolean exist(char[][] board, String _word) {
        m = board.length;
        n = board[0].length;
        visit = new boolean[m][n];
        word = _word.toCharArray();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word[0]) {
                    visit[i][j] = true;
                    boolean ret = dfs(board, i, j,1);
                    if (ret == true) {
                        return true;
                    }
                    //以该位置为起点不太行 我们需要另辟蹊径
                    visit[i][j] = false;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, int i, int j, int pos) {
        if(pos >= word.length) {
            return true;
        }
        //利用向量来解化
        int[] dx = {0,0,-1,1};
        int[] dy = {1,-1,0,0};
        for(int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >=0 && y < n && board[x][y] == word[pos] && visit[x][y] == false) {
                visit[x][y] = true;
                boolean ret = dfs(board, x, y, pos + 1);
                if(ret == true) {return true;}
                visit[x][y] = false;
            }
        }
        return false;
    }*/

}
